The present invention relates to real-time Kalman filters and, more particularly, to novel systolic array Kalman filters which perform parallel data processing in real time, using eight-pass processing in a two-dimensional (2D) array of processing elements of N.times.(N+1) size, where N is the number of states of the dynamic system being estimated by the Kalman filter; a fault-tolerant Kalman filter has a systolic array with an additional two columns and rows, i.e. a (N+2).times.(N+3) array.
The Kalman filter is well known to be an optimal recursive least-squares estimator for linear dynamical systems with white noise. A Kalman filter updates the state estimation based on prior state estimates and inputs of observed (measured) system variables. The system variables are measured in real-time (i.e. as they occur) so that system variable data can be directly input to the Kalman filter and need not be stored. The conventional filter requires input of all the associated matrices; the system dynamics, the measurement dynamics and the system noise behavior must all be known for a discrete time-varying Kalman filter to properly calculate the propagation of state estimates and error-covariance matrices between successive time samples. Many digital signal processing applications require the real time computation of the Kalman filter, e.g., tracking an aircraft with radar. Consequently, many papers have been published on the use of parallel processing technology in the form of systolic arrays for fast computation of the Kalman filter. Unfortunately, the Kalman filter cannot be pipelined since the result of the last equation is needed as input for the first equation. This results in an excess of hardware with many processors idle at any given time. In another approach (see e.g. Jet Propulsion Laboratory's Innovation Report NPO-17108/6624), the equations are reformulated such that eight applications of the Faddeev algorithm produce the desired result. Thus the systolic array is programmed for the Faddeev algorithm and the data flows through the array eight times during each iteration of the Kalman filter. However, the Faddeev algorithm requires doubling the dimension of the matrices (i.e. requiring the use of a 2N.times.2N systolic array of parallel processors), and consequently the systolic array takes more processing elements and time steps than necessary. It is desirable to provide a new systolic array implementation of the Kalman filter that is not excessive in either hardware (e.g. having about N.times.(N+1) processors in a fixed-size systolic array) or computation steps (i.e. having about 4N+6M computational steps, where M is the number of observational components).